Digital image data must be transformed or preprocessed so that computer display terminals with various gray level capacities, laser printers, dot matrix printers, ink jet printers, etc, all having various resolutions and aspect ratios, will all render an image represented by the image data in a similar way. A preprocessor associated with or configured for each such device transforms the digital data to a form tailored to the characteristics of that particular device.
Digital Halftoning is a key component of such a preprocessor. This term refers to any process that creates the illusion of continuous-tone images from careful arrangement of binary picture elements, such as ink drops in the case of ink jet printers. The process is also called spatial dithering.
One of the problems with known halftoning techniques is transient behavior near edges or boundaries. This also may be referred to as "start-up delay," and is evident where the first portion of an image to be processed has a very low gray value. Since several of the initial pixels have gray values lower than the error diffusion threshold value, no dots are fired for a time. A first dot will be fired after the accumulated error exceeds the threshold value. The need remains for a halftoning technique that minimizes or eliminates start-up delay transients.
Another common problem with known halftoning techniques is directional hysteresis due to the raster order of processing. This is particularly apparent in very light and very dark patterns. The normal (unidirectional) raster processing order also exacerbates start-up delay anomalies. A "serpentine" or boustrophedonic raster has been suggested to break-up the directionality of a normal raster without the expense of a full two-dimensional buffer. Since neighborhood operations generally buffer image data in full lines, a serpentine raster process does not require increased memory over a normal raster. Nonetheless, a serpentine raster order can itself introduce visible patterns or anomalies which would not otherwise be present in the rendered image. The need remains therefore for reducing or eliminating anomalies that result from the conventional raster ordered processing.
Known error diffusion techniques are computationally intensive and therefore time consuming. For example, even the relatively simply Floyd and Steinberg technique requires, for each pixel, calculation of four separate error terms, weighted according to the filter, and then adding those error terms to the four corresponding neighboring pixels. Other error diffusion filters require processing a greater number of terms, for example, the twelve error terms required by the Stucki filter. The need remains, therefore, for error diffusion in a manner that creates a high quality output image while minimizing processing time.
Another problem with known halftoning methods are the unsightly patterns, clusters and "worm" anomalies that appear in a rendered image in areas where the source image is of constant gray value or nearly so. While some patterns are unobtrusive and an element of subjective judgment is involved in any case, the need remains nonetheless for improved output image quality in halftoned systems.